# quick_sort.py



# 32 18 8 19 5 19 2 199
# left              right


# 快排是不稳定的，可以想象一下，如果 右边有两个相等的元素比temp小，后面的数最先交换到pivot的左边,破坏稳定性
def partition(data, left, right):
    temp = data[left]

    while left < right:
        # data[right] == temp也需要移动，为啥?
        # 为啥这里要求left < right? - 如果列表本来就是有序的 right移动到left时任然满足条件right会变负数越界
        while left < right and data[right] >= temp:
            right -= 1
        
        data[left] = data[right]

        while left < right and data[left] <= temp:
            left += 1
        
        data[right] = data[left]
    
    # 这里left == right
    data[left] = temp
    return left
        


def quick_sort(data, left, right): # 开始left = 0 right = len(data)-1
    if left < right: # 至少有两个元素 递归终止条件
        # 分割获得中间元素的节点位置
        mid = partition(data, left, right)
        quick_sort(data, left, mid-1)
        quick_sort(data, mid+1, right)


import random
data = [random.randint(0, 100) for _ in range(100)]
print(data)
quick_sort(data, 0, len(data)-1)
print(data)